package com.zlk.algorithm.algorithm.dynamicPlan.twoDimension.more;

import cn.hutool.core.text.escape.NumericEntityUnescaper;
import com.zlk.algorithm.algorithm.sort.heap.Test;

// 交错字符串
// 给定三个字符串 s1、s2、s3
// 请帮忙验证s3是否由s1和s2交错组成
// 测试链接 : https://leetcode.cn/problems/interleaving-string/
public class Code03_InterleavingString {

    public static void main(String[] args) {
        Code03_InterleavingString test = new Code03_InterleavingString();
        test.isInterleave("aabcc","dbbca","aadbbcbcac");
    }

    /**
     * 思路分析
     * 首先暴力尝试，穷举所有可能性分析
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public boolean isInterleave(String s1, String s2, String s3) {
       // return f2(s1.toCharArray(),s2.toCharArray(),s3.toCharArray());
        return f3(s1.toCharArray(),s2.toCharArray(),s3.toCharArray());
    }

    private boolean f3(char[] s1, char[] s2, char[] s3) {
        if (s1.length + s2.length != s3.length) {
            return false;
        }
        int l1 = s1.length;
        int l2 = s2.length;
        boolean[] dp = new boolean[l2+1];
        for (int i = 0; i <=l1; i++) {
            for (int j = 0; j<=l2 ; j++) {
                if(i==0&&j==0){
                    dp[0] = true;
                }else{
                    int l3 = i+j;
                    if(i>0&&s1[i-1]!=s3[l3-1]&&j>0&&s2[j-1]!=s3[l3-1]){
                        dp[j] = false;
                    }else{
                        boolean p1 = false;
                        if(i>0&&s1[i-1]==s3[l3-1]){
                            p1 = dp[j];
                        }
                        boolean p2 = false;
                        if(j>0&&s2[j-1]==s3[l3-1]){
                            p2 = dp[j-1];
                        }
                        dp[j] = p1||p2;
                    }
                }

            }
        }
        return dp[l2];
    }


    //  情况1
    //       s1[i-1]==s3[i+j-1]  找  f(i-1,j)
    //  情况2 s2[j-1]==s3[i+j-1]  找 f(i,j-1);
    private boolean f2(char[] s1, char[] s2, char[] s3) {
        if (s1.length + s2.length != s3.length) {
            return false;
        }
        int l1 = s1.length;
        int l2 = s2.length;
        boolean[][] dp = new boolean[l1+1][l2+1];
        for (int i = 0; i <=l1; i++) {
            for (int j = 0; j<=l2 ; j++) {
                if(i==0&&j==0){
                    dp[0][0] = true;
                }else{
                    int l3 = i+j;
                    if(i>0&&s1[i-1]!=s3[l3-1]&&j>0&&s2[j-1]!=s3[l3-1]){
                        dp[i][j] = false;
                    }else{
                        boolean p1 = false;
                        if(i>0&&s1[i-1]==s3[l3-1]){
                            p1 = dp[i-1][j];
                        }
                        boolean p2 = false;
                        if(j>0&&s2[j-1]==s3[l3-1]){
                            p2 = dp[i][j-1];
                        }
                        dp[i][j] = p1||p2;
                    }
                }

            }
        }
        return dp[l1][l2];
    }


    private boolean f1(char[] s1, char[] s2, char[] s3, int l1, int l2) {
        //base case
        if(l1==0&&l2==0){
            return true;
        }
        int l3 = l1+l2;
        boolean p1 = false;
        if(l1>0&&s1[l1-1]==s3[l3-1]){
            p1 = f1(s1,s2,s3,l1-1,l2);
        }
        boolean p2 = false;
        if(l2>0&&s2[l2-1]==s3[l3-1]){
            p2 = f1(s1,s2,s3,l1,l2-1);
        }
        return p1||p2;
    }


}
